/**
 * 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 */

/**
 * 1.两个两个比较
 * 将第一个字符串拿出来, 然后再循环后面的字符串, 一个一个比较, 若有重复前缀的, 更新一开始记录的字符串
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 *
 * 2. 一下子整体比较
 * 先要求得他们中最短的长度是多少, 不然后面整体遍历不知道结束条件, 肯定会有短的字符串越界的
 * 然后再分别取他们的每一个字符比较, 全都相同就可以存进相同前缀字符串了
 * 这里有两种判断是否全部相同的方法
 * 2.1 可以定义一个变量 tmp = true , 一有不相同的就置为 false, 并在最外围的循环中判断最终结果
 * 2.2. 可以定义一个长度为 26的 hash数组, 并遍历, 并在对应的位置 ++, 最后只要判断最后对应的位置是否为 strs长度就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 */

public class Main {

    // **********************************************************************
    // 1. 两个两个做比较
    public String longestCommonPrefix(String[] strs) {

        if(strs == null||strs.length == 0){
            return "";
        }

        String s = strs[0];
        int length = strs.length;
        for (String str : strs) {

            // 两两查找最长公共字符串
            s = getCommon(s, str);

            // 如果公共字符串为空, 直接退出循环
            if (s.isEmpty()) {
                break;
            }
        }

        return s;

    }

    /**
     * 求得最长公共字符串
     *
     * @param s
     * @param str
     * @return
     */
    public String getCommon(String s, String str){

        // 求出两个字符串的最小长度, 避免数组越界
        int length = Math.min(s.length(),str.length());

        // 记录公共长度
        int index = 0;
        while (index < length && s.charAt(index)==str.charAt(index)){
            index++;
        }

        return s.substring(0,index);
    }

    // ***********************************************************************
    // 2.1 一下子整体比较
    public String longestCommonPrefix2(String[] strs) {

        // 定义字符串拼接函数
        StringBuffer ret = new StringBuffer();

        // 求字符创中的最小长度
        int n = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            n = Math.min(strs[i].length(), n);
        }

        // 要限制循环次数, 避免数组越界
        for (int i = 0; i < n; i++) {

            // 判断是否全都相同的条件, 初始化为 true, 后面好判断
            boolean tmp = true;

            // 求出第一个的每个字符来用做对比
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {

                // 求出剩下字符串的字符
                char curc = strs[j].charAt(i);

                // 如果有一个字符不相同, 直接返回false, 并退出循环
                if (curc != c) {
                    tmp = false;
                    break;
                }
            }

            // 判断是否相同
            if (tmp) {

                // 相同拼接
                ret.append(c);
            } else {

                // 不相同直接退出循环
                break;
            }
        }

        // 不要忘记转化为字符串
        return ret.toString();
    }

    // ********************************************************************
    // 2.2一下子整体比较 2.0
    public String longestCommonPrefix3(String[] strs) {

        // 定义字符串拼接函数
        StringBuffer ret = new StringBuffer();

        // 求字符创中的最小长度
        int n = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            n = Math.min(strs[i].length(), n);
        }

        // 要限制循环次数, 避免数组越界
        for (int i = 0; i < n; i++) {

            // 定义 hash数组, 用来记录是否全都相等
            int[] hash = new int[26];

            // 将每个字符对应的下标在 hash位置中 ++
            for (String s : strs) {
                int in = s.charAt(i) - 'a';
                hash[in]++;
            }

            // 如果 hash中对应的值等于 strs的长度, 就全都相同, 可以添加
            // 不相同, 就要退出循环
            char c = strs[0].charAt(i);
            if (hash[c - 'a'] != strs.length) {
                break;
            }
            ret.append(c);
        }

        // 不要忘记转化为字符串
        return ret.toString();
    }
}